package interview;

import java.util.LinkedList;
import java.util.List;

public class interview_08_07 {
    public String[] permutation(String S) {
        int len=S.length();
        if(len==0) return new String[0];
        boolean[] flag=new boolean[len];
        List<String> list=new LinkedList<>();
        StringBuilder stringBuilder=new StringBuilder();
        char[] s=S.toCharArray();
        search(list,stringBuilder,0,flag,s);
        String[] result=new String[list.size()];
        for(int i=0;i<list.size();++i){
            result[i]=list.get(i);
        }
        return result;
    }
    public void search(List<String> list,StringBuilder stringBuilder,int num,boolean[] flag,char[] s){
        if(num== flag.length){
            list.add(stringBuilder.toString());
            return;
        }
        for(int i=0;i< flag.length;++i){
            if(!flag[i]){
                stringBuilder.append(s[i]);
                flag[i]=true;
                search(list, stringBuilder, num+1, flag, s);
                stringBuilder.deleteCharAt(num);
                flag[i]=false;
            }
        }
    }
}
